翻訳と辞書 Words near each other ・ Karatobe, Almaty Region ・ Karatodai Station ・ Karatoo ・ Karatoula ・ Karatoula, Elis ・ Karatoulas ・ Karatoya River ・ Karats ・ Karatsu Castle ・ Karatsu Domain ・ Karatsu Kunchi ・ Karatsu Line ・ Karatsu Station ・ Karatsu ware ・ Karatsu, Saga ・ Karatsuba algorithm ・ Karattadipalayam ・ Karattupalayam ・ Karattuppatti ・ Karatu (Tanzanian ward) ・ Karatu District ・ Karaturyk ・ Karatuzsky ・ Karatuzsky District ・ Karatëbë ・ Karaudia ・ Karaugh Brown ・ Karaul ・ Karaula ・ Karaula (Ilijaš) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Karatsuba algorithm ： ウィキペディア英語版 Karatsuba algorithm The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962.〔 〕〔 〕〔 Knuth D.E. (1969) ''The Art of Computer Programming. v.2.'' Addison-Wesley Publ.Co., 724 pp. 〕 It reduces the multiplication of two ''n''-digit numbers to at most $n^\backslash approx\; n^$ single-digit multiplications in general (and exactly $n^$ when ''n'' is a power of 2). It is therefore faster than the classical algorithm, which requires ''n''2 single-digit products. For example, the Karatsuba algorithm requires 310 = 59,049 single-digit multiplications to multiply two 1024-digit numbers (''n'' = 1024 = 210), whereas the classical algorithm requires (210)2 = 1,048,576. The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm. The Toom–Cook algorithm is a faster generalization of Karatsuba's method, and the Schönhage–Strassen algorithm is even faster, for sufficiently large ''n''. ==History== The standard procedure for multiplication of two ''n''-digit numbers requires a number of elementary operations proportional to $n^2\backslash ,\backslash !$, or $\backslash Theta(n^2)\backslash ,\backslash !$ in the big-O notation. In 1952, Andrey Kolmogorov conjectured that the classical algorithm was ''asymptotically optimal,'' meaning that any algorithm for that task would require $\backslash Omega(n^2)\backslash ,\backslash !$ elementary operations. In 1960, Kolmogorov organized a seminar on mathematical problems in cybernetics at the Moscow State University, where he stated the $\backslash Omega(n^2)\backslash ,\backslash !$ conjecture and other problems in the complexity of computation. Within a week, Karatsuba, then a 23-year-old student, found an algorithm (later it was called "divide and conquer") that multiplies two ''n''-digit numbers in $\backslash Theta(n^)$ elementary steps, thus disproving the conjecture. Kolmogorov was very agitated about the discovery; he communicated it at the next meeting of the seminar, which was then terminated. Kolmogorov did some lectures on the Karatsuba result at the conferences all over the world (see, for example, "Proceedings of the international congress of mathematicians 1962", pp. 351--356, and also "6 Lectures delivered at the International Congress of Mathematicians in Stockholm, 1962") and published the method in 1962, in the Proceedings of the USSR Academy of Sciences. The article had been written by Kolmogorov and contained two results on multiplication, Karatsuba's algorithm and a separate result by Yuri Ofman; it listed "A. Karatsuba and Yu. Ofman" as the authors. Karatsuba only became aware of the paper when he received the reprints from the publisher.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Karatsuba algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.